public class Test {
    public static void main(String[] args) {
        Integer[] arr = {1,5,2,4,7,0,9,6};
        Merge.sort(arr);
        for (int i:arr) {
            System.out.println(i);
        }
    }
}


class Merge {
    //辅助数组
    private static Comparable[] assist;

    //比较v是否比m小
    private static boolean less(Comparable v, Comparable m) {
        return v.compareTo(m) < 0;
    }

    //数组元素i和j交换位置
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    //对数组a中的元素进行排序
    public static void sort(Comparable[] a) {
        assist = new Comparable[a.length];
        int low = 0;
        int high = a.length - 1;
        sort(a, low, high);
    }

    private static void sort(Comparable[] a, int low, int high) {
        //安全性校验
        if (high <= low) {
            return;
        }
        int mid = low + (high - low) / 2;
        sort(a, low, mid);
        sort(a, mid + 1, high);
        merge(a, low, mid, high);
    }

    private static void merge(Comparable[] a, int low, int mid, int high) {
        int i = 0;
        int left = low;
        int right = mid + 1;
        while(left <= mid && right <= high){
            if(a[left].compareTo(a[right]) < 0){
                assist[i++] = a[left++];
            }else {
                assist[i++] = a[right++];
            }
        }
        while(left <= mid){
            assist[i++] = a[left++];
        }
        while(right <= high){
            assist[i++] = a[right++];
        }
        for (int j = 0; j < i; j++) {
            a[j+low] = assist[j];
        }
    }
}
